package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 337. 打家劫舍 III
 * @date 2025/2/25 23:05
 */
public class E337 {

    /**
     * <h3>方法一：动态规划</h3>
     * @param root 节点
     * @return 偷到的最大金额
     */
    public int rob(TreeNode root) {
        int[] result = robAction(root);
        return Math.max(result[0], result[1]);
    }

    /**
     * 动态规划的思想
     * @param root 节点
     * @return 偷到的最大金额数组，0表示不偷头节点，1表示偷头节点
     */
    private int[] robAction(TreeNode root) {
        int[] result = new int[2];
        // 1. 递归结束条件，没有节点，想偷也偷不了
        if (root == null) return result;
        // 2. 抢左子树的两种情况的最大金额
        int[] leftMax = robAction(root.left);
        // 3. 抢右子树的两种情况的最大金额
        int[] rightMax = robAction(root.right);
        // 4. 当前树不抢头节点的情况的最大金额，左右子树的头节点可抢可不抢
        result[0] = Math.max(leftMax[0], leftMax[1]) + Math.max(rightMax[0], rightMax[1]);
        // 5. 当前树抢头节点的情况的最大金额，左右子树头节点不可抢
        result[1] = root.val + leftMax[0] + rightMax[0];
        // 6. 返回当前树两种情况的最大金额
        return result;
    }
}
